package com.ly.algorithm.leetcode.tree;

import	java.util.Stack;


import java.util.*;

/**
 * @Classname Problem145
 * @Description
 * 给定一个二叉树，返回它的 后序 遍历。
 *
 * 示例:
 *
 * 输入: [1.txt,null,2,3]
 *    1.txt
 *     \
 *      2
 *     /
 *    3
 *
 * 输出: [3,2,1.txt]
 *

 * @Date 2020/9/29 11:21
 * @Author 冷心影翼
 */
public class Problem145 {

	public static void main(String[] args) {
		Solution145 solution145 = new Solution145();
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.left.right = new TreeNode(3);
//		List<Integer> list = solution145.postorderTraversal(root);
		List<Integer> list = solution145.postorderTraversalByStack(null);
		System.out.println(list);
	}
}


class Solution145 {
	public List<Integer> list = new ArrayList<>();

	public List<Integer> postorderTraversal(TreeNode root) {
		postorder(root);
		return list;
	}

	public List<Integer> postorderTraversalByStack(TreeNode root) {
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		while (stack.size()>0 && root != null) {
			root = stack.pop();
			if(root.left!=null)
				stack.push(root.left);
			if(root.right!=null)
				stack.push(root.right);
			list.add(0,root.val);
		}
		return list;
	}

	public List<Integer> preorderTraversalByStack(TreeNode root) {
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		while (stack.size()>0 && root != null) {
			root = stack.pop();
			if(root.left!=null)
				stack.push(root.left);
			if(root.right!=null)
				stack.push(root.right);
			list.add(0,root.val);
		}
		return list;
	}

	public void postorder(TreeNode root) {
		if(root == null) {
			return;
		}
		postorder(root.left);
		postorder(root.right);
		list.add(root.val);
	}



	/**
	 * 统一一下
	 * @param root
	 * @return
	 */
	//前序
	public static List<Integer> preOrder(TreeNode root){
		List<Integer> list = new ArrayList();
		Stack<TreeNode> stack = new Stack();
		TreeNode cur = root;
		while(cur!=null || !stack.isEmpty()){
			//一直往左压入栈
			while(cur!=null){
				list.add(cur.val);
				stack.push(cur);
				cur = cur.left;
			}
			cur = stack.pop();
			cur = cur.right;
		}
		return list;
	}


	//中序
	public List<Integer> inorderTraversal(TreeNode root) {
		if(root == null){
			return new ArrayList();
		}
		List<Integer> list = new ArrayList();
		Stack<TreeNode> stack = new Stack();
		TreeNode cur = root;
		while(cur != null || !stack.isEmpty()){
			while(cur!=null){
				stack.push(cur);
				cur = cur.left;
			}
			cur = stack.pop();
			list.add(cur.val);
			cur = cur.right;
		}
		return list;
	}


	//后序遍历，非递归
	public static List<Integer> postOrder(TreeNode root){
		Stack<TreeNode> stack = new Stack<>();
		List<Integer> list = new ArrayList<>();
		TreeNode cur = root;
		TreeNode p = null;//用来记录上一节点
		while(!stack.isEmpty() || cur != null){
			while(cur != null){
				stack.push(cur);
				cur = cur.left;
			}
			cur = stack.peek();
//            后序遍历的过程中在遍历完左子树跟右子树cur都会回到根结点。所以当前不管是从左子树还是右子树回到根结点都不应该再操作了，应该退回上层。
//            如果是从右边再返回根结点，应该回到上层。
			//主要就是判断出来的是不是右子树，是的话就可以把根节点=加入到list了
			if(cur.right == null || cur.right == p){
				list.add(cur.val);
				stack.pop();
				p = cur;
				cur = null;
			}else{
				cur = cur.right;
			}

		}
		return list;
	}
}


